1. Field of the Invention
The present invention relates in general to computer-aided design tools for generating hierarchical integrated circuit (IC) layouts, and in particular to a method for synthesizing a clock tree for a hierarchically partitioned IC layout.
2. Description of Related Art
Hierarchical IC Layouts
A xe2x80x9ccell libraryxe2x80x9d is a data base of models of various circuit components (xe2x80x9ccellsxe2x80x9d) an integrated circuit (IC) designer can incorporate into an IC design. The cell library includes behavioral models of each cell and also a physical model of each cell showing placement and routing (PandR) tools how the cell is to be laid out in an a semiconductor substrate when included in an IC.
An IC designer typically creates a xe2x80x9cnetlistxe2x80x9d describing the IC by referencing the library cells forming it and indicating how the terminals of the cells are logically interconnected. After having created the netlist, and having used a circuit simulator and other tools to the verify the behavior of the circuit described by the netlist, an IC designer typically provides the netlist as input to an automated PandR tool which designs the physical layout of the IC on a semiconductor substrate. The PandR tool consults the cell library to determine how to lay out each cell described by the netlist and then determines where to place each cell in the substrate and how to form signal, power and ground paths for connecting the cells to one another.
The netlist that the designer produces usually describes an IC as a hierarchy of modules. For example as illustrated in FIG. 1, the netlist may consider an entire IC design to be a single top level (level 1) module M0. A set of three level 2 modules M1-M3 and some individual cells 10 not included in any of modules M1-M3 form module M0. Each module M1-M3 may in turn be formed by level 3 modules or cells. In the example of FIG. 1, module M2 includes a set of four level 3 modules M4-M7 and some individual cells 11 not included in any of modules M4-M7. Modules M4-M7 reside at the lowest level (level 3) of the modular hierarchy because they are formed only by base level cells 12 which are not organized into submodules. Although FIG. 1 illustrates a circuit design having only a few modules organized into a three hierarchical levels, a large IC design may include hundreds or thousands of modules organized into many more hierarchical levels.
An IC designer organizes a IC design as a hierarchy of modules to make it easier to conceptualize the IC. However since a typical PandR tool is interested only in finding a suitable position for each cell of the design, it ignores the modularity of the design and places each cell wherever it is convenient to do so and does not try to keep all of the cells of a given module within a separately identifiable area of a semiconductor substrate. Hence the cells forming various modules of a hierarchical design usually end up being intermingled to some extent in an IC layout.
Partitioned Layouts
A designer may want to produce a xe2x80x9cpartitionedxe2x80x9d IC layout in which one or more selected modules are to be placed in separate partitions of a substrate. For example FIG. 2 illustrates a floor plan for a semiconductor substrate 16 upon which the IC of FIG. 1 may be formed. FIG. 1 illustrates how the IC layout of FIG. 1 might be partitioned. In this example, module M1 is placed within partition P1, modules M5 and M7 are placed within partition P2, modules M4 and M6 are placed in partitions P3 and P4, respectively. All modules and cells not included in any xe2x80x9cbase levelxe2x80x9d partition P1-P4 (in this example only module M3 and cells 10 and 11 of modules M0 and M2_) may be placed anywhere within a xe2x80x9ctop levelxe2x80x9d partition P0. For simplicity partitions P0-P4 are illustrated as being rectangular, but partitions may be of more complicated shapes. Given a pin assignment plan indicating the places along the boundaries of the various partition where signal paths are to cross between partitions, PandR tools can independently lay out each partition, provided that they are able to keep the layouts within the partition boundaries specified by the floor plan.
It can be advantageous to partition a design because a PandR tool can often separately layout several partitions of a design faster than it can lay out an unpartitioned design. Also when a designer places a selected module of a design in an identifiable area of a substrate so that its cells are not intermingled with cells of other modules, the designer may be able to later modify that particular module without greatly affecting the layout of other modules. However, as discussed below, problems associated with clock tree synthesis tend to increase the interdependence of partition layouts, thereby complicating the layout process after one partition is changed.
Clock Tree Synthesis
Digital ICs typically implement synchronous logic circuits that are clocked by externally generated clock signals. For example FIG. 3 shows a simple example of a synchronous logic circuit within an IC 30. A latch 30 latches two IC input signals A and B onto inputs of a logic circuit 34 and an IC input signal C onto an input of a logic circuit 36. Logic circuit 34 carries out logic operations on signals A and B to produce an output signal D latched onto another input of logic circuit 36 by a latch 38. Logic circuit 36 processes signals C and D to form a signal E, and a latch 39 latches signal E onto an output terminal of IC 30. A CLOCK signal supplied as input to IC 30 clocks all of latches 30, 38 and 39. For the circuit to operate synchronously, it is necessary to route the CLOCK signal to each latch 36, 38 and 39 in such a way that edges of the CLOCK signal arrive substantially at the same time at all latches.
While FIG. 3 shows only three devices being clocked by the CLOCK signal, a typical IC can have hundreds or thousands of clocked devices (xe2x80x9csyncsxe2x80x9d) such as latches, registers and flip-flops. After a PandR tool has generated an IC layout in which all of the cells (including all of the syncs) have been placed and routed, a xe2x80x9cclock tree synthesisxe2x80x9d tool designs a clock tree for routing CLOCK edges from the IC""s clock input terminal concurrently to all syncs.
FIG. 4 is a schematic diagram illustrating a clock tree 40 for delivering a CLOCK signal from an IC input pin 42 to several syncs 44. FIG. 5 illustrates positions of syncs 44 within an IC substrate 46 after a PandR tool has generated a full-chip IC layout. A typical clock tree synthesis tool begins designing the clock tree of FIG. 4 by assigning each sync 44 into one of a set of xe2x80x9cclustersxe2x80x9d 48 as illustrated in FIG. 6. The clock tree will deliver the CLOCK signal to the syncs 44 of each cluster 48 through a separate one of signal buffers 50 (FIG. 4), and therefore each cluster 48 will include no more than the maximum number of syncs 44 a single buffer 50 can drive. To ensure that CLOCK signal edges travel from the output of each buffer 50 to all syncs 44 it drives with as nearly as possible the same delay, the clock tree synthesis tool groups only nearby syncs 44 into the same cluster 48. This ensures that the CLOCK signal path distance from each buffer 50 to the syncs it drives will be substantially similar regardless of where the buffer is placed.
Having grouped all syncs 44 into clusters and having specified an approximate location for each buffer 50 near the cluster it drives, the synthesis tool next groups nearby buffers 50 into clusters. As illustrated in FIG. 4, the CTS tool has grouped twelve buffers 50 into four clusters 52. The CTS tool then provides a separate buffer 54 to drive each cluster 52 of buffers 50. After specifying an approximate location for each second level buffer 54 near the cluster of first level buffers 50 it is to drive, the CTS tool groups buffers 54 into clusters 56, each driven by a separate buffer 58. All buffers 58 are then grouped into a single cluster 60 to be driven by a single buffer 62. The result is a hierarchical clock tree 40 having four levels of buffers 50, 54, 58 and 62.
Having laid out the basic framework of clock tree 40, the CTS tool next must xe2x80x9cbalancexe2x80x9d the clock tree to ensure that each CLOCK signal edge arrives at all syncs 44 at as nearly as possible the same time, thereby substantially zeroing the CLOCK signal skew between syncs 44. To do so the CTS tool may insert additional buffers 64 into various branches of tree 40, since adding a buffer 64 to a branch reduces the signal path delay through that branch. The CTS tool may also adjust the size of selected buffers in each clock signal path; large buffers switch faster than small buffers and therefore propagate CLOCK signal edges faster. A CTS tool may also make fine adjustments to path delays by adjusting the positions of the buffers along a path. By adjusting the number, size and positions of buffers within each branch of clock tree 40, a xe2x80x9czero skewxe2x80x9d CTS tool can synchronize the arrival of CLOCK signal edges at a large number of syncs with a high degree of accuracy.
FIG. 7 illustrates the steps in a conventional process for producing an IC layout when a design has been partitioned. The first step (step 70) is to create a floor plan reserving a separate area of the substrate for each partition P0-P4 of the design and a pin assignment plan indicating points at which signal are to cross boundaries of each partition. PandR tools then separately lay out each partition P0-P4 (step 72). After the partition layouts are combined to form a full-chip layout (step 74), a CTS tool synthesizes a clock tree for the entire IC (step 76). As it synthesizes a clock tree, the CTS tool establishes only an approximate position for each buffer forming the clock tree and only approximates the routing of signal paths that will link the buffers to one another and to the syncs so that it can make reasonably accurate estimates of signal path delays through the clock tree. After the CTS tool has established approximate positions of clock tree buffers and signal paths, the PandR tool must globally adjust the layout of the entire IC to position each buffer forming the clock tree and to detail the routing of the signal paths that interconnect the buffers and syncs (step 78). In doing so, the PandR tool may move some of the cells forming the IC to make room for the clock tree buffers and clock tree signal routing paths. Thus even though a PandR tool may be able to separately lay out each partition of a design and then assemble the partitions into a full-chip layout, it must reprocess the entire full-chip layout at step 78, including the layout of each partition, following clock tree synthesis in order to place and route the buffers and signal paths forming the clock tree.
Conventional CTS tools operate only after the partitions have been merged because they must have a global view of clock signal path delays throughout the entire IC in order to balance the clock tree. Therefore, should the designer make a change to any partition of an IC design after the layout process is complete, it necessary for the designer to adjust not only the layout of that partition, but to also adjust the layout of every other partition of the design to accommodate global changes that a CTS tool might make in a clock tree when any small part of a layout changes. Thus while IC designs can initially be divided into partitions that can be separately laid out, any subsequent change to any partition that affects a clock tree can make it necessary to adjust the layout of every other partition.
What is needed is a clock tree synthesis system that can partition the design of a clock tree along the same lines that an IC is partitioned for layout purposes so that a change to the layout of any one partition requiring a change in the portion of the clock tree residing within that partition would not affect portions of the clock tree residing within any other partition and would therefore not require a change to the layout of any other partition.
The invention relates to a method and apparatus for synthesizing a clock tree for a partitioned integrated circuit (IC) layout, wherein the layout includes a plurality of base level partitions and a top level partition, with each partition occupying a separate area of a semiconductor substrate. Each base level partition includes several syncs to be clocked by edges of a clock signal applied to an entry node within the area occupied by the top level partition.
In accordance with the invention, a subtree is separately synthesized for each base level partition. The subtree for each base level partition includes a start point at a perimeter of the area occupied by that partition and a network of buffers and signal paths for conveying a clock signal edge from the start point to each sync included within that area. The subtree for each base level partition is balanced so that it delivers each clock signal edge arriving at its start point to each sync within the base level partition with a substantially similar delay. However the subtrees for the separate base level partitions are separately and independently balanced and will normally have substantially differing average clock signal path delays between their start points and the syncs they clock.
After the clock tree for each base level partition is synthesized, a top level portion of the clock tree is synthesized. The top level portion of the subtree resides within the substrate area containing the top level partition and conveys the clock signal from the IC clock signal entry point to the start point of each synthesized subtree. Clock signal paths within the top level portion of the subtree are adjusted to compensate for differences in the average path delays of the subtrees so that the clock tree conveys each clock signal edge arriving at the IC entry point to every sync with substantially the same delay.
Once the clock tree has been synthesized, it is possible to re-synthesize the top level portion of the clock tree and the subtree for any one base level partition to accommodate a change in the layout of that one base level partition. It is not necessary to modify the subtree for any other base level partition.
Accordingly it is an object of the invention to provide a system for synthesizing a clock tree for a partitioned IC design, wherein changes in the layout of any base level partition do not necessitate changes to portions of the clock tree serving syncs residing in any other base level partition.
The claims appended to this specification particularly point out and distinctly claim the subject matter of the invention. However those skilled in the art will best understand both the organization and method of operation of what the applicant(s) consider to be the best mode(s) of practicing the invention, together with further advantages and objects of the invention, by reading the remaining portions of the specification in view of the accompanying drawing(s) wherein like reference characters refer to like elements.